package 记忆化搜索;

import java.util.Arrays;

//零钱兑换2
public class Solution9 {
    public int change(int amount, int[] coins) {
        mem = new int[coins.length][amount + 1];
        for (int i = 0 ; i < coins.length ; i++) Arrays.fill(mem[i], -1);
        return dfs(0, 0, amount, coins);
    }
    int[][] mem;
    private int dfs(int idx, int sum, int amount, int[] coins) {
        if (sum >= amount || idx >= coins.length) return sum == amount ? 1 : 0;
        if (mem[idx][sum] != -1) return mem[idx][sum];
        int ans = dfs(idx + 1, sum, amount, coins) + dfs(idx, sum + coins[idx], amount, coins);
        mem[idx][sum] = ans;
        return ans;
    }
}